\chapter{Derivation of NRMSE of NUFFT with Linear Interpolation}

With linear interpolation, $g_l(x)$ on the interval $[x_k, x_{k+1}]$ is represented by:
\begin{align}
    g_l(x) &= \frac{g_l(x_{k+1})-g_l(x_k)}{h} \left( x - x_k \right)
    + g_l(x_k) \label{eq:linear-G}
\end{align}
where $h=x_{k+1}-x_k$.

The total error on the interval $[x_k, x_{k+1}]$ is:
\begin{align}
    R(n,k) &= \int _{x_k} ^{x_{k+1}} \left| e^{\imath \frac{2 \pi n}{N}x}
    - s_n^{-1} \sum _{l=-\lfloor (J-1)/2 \rfloor} ^{\lceil (J-1)/2 \rceil}
    \left[ \frac{g_l(x_{k+1})-g_l(x_k)}{h} \left( x - x_k \right) + g_l(x_k)
    \right] e^{\imath \frac{2 \pi n}{mN}l} \right| ^2 dx \notag \\
    &= \int _{0} ^{h} \left| e^{\imath \frac{2 \pi n}{N}x_k}
    e^{\imath \frac{2 \pi n}{N}x}
    - s_n ^{-1} \sum _{l=-\lfloor (J-1)/2 \rfloor} ^{\lceil (J-1)/2 \rceil}
    \left[ \frac{g_l(x_{k+1})-g_l(x_k)}{h} x + g_l(x_k)
    \right] e^{\imath \frac{2 \pi n}{mN}l} \right| ^2 dx \notag \\
    \label{eq:Error-in-k}    
\end{align}
Let 
\begin{align*}
    A_{nk} &= e^{\imath \frac{2 \pi n}{N}x_k} \\
    B_{nk} &= - s_n ^{-1} \sum _{l=-\lfloor (J-1)/2 \rfloor} ^{\lceil (J-1)/2 \rceil} \frac{g_l(x_{k+1})-g_l(x_k)}{h} e^{\imath \frac{2 \pi n}{mN}l} \\
    C_{nk} &= - s_n ^{-1} \sum _{l=-\lfloor (J-1)/2 \rfloor} ^{\lceil (J-1)/2 \rceil} g_l(x_k) e^{\imath \frac{2 \pi n}{mN}l}
\end{align*}
then,
\begin{align}
    R(n,k) &= \int _{0} ^{h} \left| A_{nk} e^{\imath \frac{2 \pi n}{N}x}
    + B_{nk} x + C_{nk} \right| ^2 dx \notag \\
    &= h + I_1(n,k) + I_2(n,k) + I_3(n,k)
    \label{eq:Error-in-k-Analytical}
\end{align}
where
\begin{align*}
    I_1(n,k) &= 2\Real \left\{ A_{nk}B_{nk}^{*} \int _{0}^{h} x
    e^{\imath \frac{2 \pi n}{N}x} dx \right\} \\
    I_2(n,k) &= 2\Real \left\{ A_{nk}C_{nk}^{*} \int _{0}^{h}
    e^{\imath \frac{2 \pi n}{N}x} dx \right\} \\
    I_3(n,k) &= \frac{1}{3} \| B \| ^2 h ^3
    + \Real \left\{ B_{nk} C_{nk}^{*} \right\} h^2
    + \|C \| ^2
\end{align*}

For $\alpha \ne 0$,
\begin{align*}
    \int _0 ^h x e^{\alpha x} dx
    &= \frac{h}{\alpha} e^{\alpha h}
    - \frac{1}{\alpha ^2}
    \left( e^{\alpha h}-1\right) \\
    \int _0 ^h e^{\alpha x} dx
    &= \frac{1}{\alpha} \left( e^{\alpha h}-1\right)
\end{align*}